package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description: 421. Maximum XOR of Two Numbers in an Array
 * @author: STU756
 * @create: 2020-08-16 22:55
 */
public class Pro0421 {
    static final int N = 3000010;
    static int[][] son;
    static int idx;

    static void insert(int x) {
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int u = (x >> i) & 1;
            if (son[u][p] == 0) son[u][p] = ++idx;
            p = son[u][p];
        }
    }

    static int maxXor(int x) {
        int p = 0;
        int res = 0;
        for (int i = 30; i >= 0; i--) {
            int u = (x >> i) & 1;
            if (son[1 - u][p] != 0) {
                res += 1 << i;
                p = son[1 - u][p];
            } else {
                p = son[u][p];
            }
        }
        return res;
    }

    public int findMaximumXOR(int[] nums) {
        son = new int[2][N];
        idx = 0;
        int res = Integer.MIN_VALUE;
        for (int num : nums) {
            insert(num);
            res = Math.max(res, maxXor(num));
        }
        return res;
    }
//    class Node{
//        Node[] node;
//        public Node(){
//            node = new Node[2];
//        }
//    }
//    Node trie = new Node();
//    //trie树
//    public int findMaximumXOR(int[] nums) {
//        //build trie tree
//        for(int num : nums) {
//            Node p = trie;
//            //int范围为 [2^31, 2^31 - 1]
//            for(int i = 30; i >= 0; i--) {
//                if(((num >> i) & 1) == 1) {
//                    if(p.node[1] == null) {
//                        p.node[1] = new Node();
//                    }
//                    p = p.node[1];
//                }else {
//                    if(p.node[0] == null) {
//                        p.node[0] = new Node();
//                    }
//                    p = p.node[0];
//                }
//            }
//        }
//
//        int ans = 0;
//
//        for(int num : nums) {
//            Node p = trie;
//            int s= 0;
//            for(int i = 30; i >= 0; i-- ) {
//                int t = (num >> i) & 1;
//                if(p.node[t^1]!=null) { //当t==0时，对应的应该取1
//                    s += 1 << i;
//                    p = p.node[t^1];
//                }else{
//                    //如果p.node[t^1]为空的时候，顺着node[0]节点下去
//                    p = p.node[t];
//                }
//            }
//            ans = Math.max(s, ans);
//        }
//
//        return ans;
//    }
}
